Navigation is a fundamental requirement for the successful use of a mobile robot. Navigation is of particular interest when the mobile robot is to be "autonomous" where "autonomous" describes the ability of the robot, once actuated, to navigate without human intervention and without dependence on artificial, either active or passive, beacons placed in its environment.
For successful navigation, an autonomous mobile robot generally will need a navigation system that includes a map of its environment. Various arrangements are known in which the robot is provided with an accurate map of its environment at the start of its travel and the environment is assumed to remain fixed during its travel. However for most autonomous robots, it is desirable to build and maintain a map of the robot's environment automatically. Moreover, even when a robot is provided with a map of its environment, it would be desirable to update automatically the map when the environment changes.
Typically, an autonomous robot determines its relationship to its environment by scanning. As used herein, scanning denotes the process of obtaining electronic signals and converting these signals into digital form from one or more active or passive sensors mounted on the robot. The process may or may not involve a physical rotation or movement of the sensors. A sensor is active if the sensory data is obtained through a process in which energy is radiated from the sensor to be reflected from a reflecting surface in the environment back to the sensor for detection. A sensor is passive if it merely detects ambient energy reflected from a reflecting object in the environment such as a camera tube. The energy involved in scanning may be ultrasonic or electromagnetic such as microwave infra-red and visible, and systems are readily available for use with any of these types. A common difficulty is in interpreting the sensed data and deciding what the sensed signals tell about the environment.
There are two distinctly different problems associated with sensing, distinguishing useful data from noise and uncertainty in the origin of the sensor measurements available.
The noise problem is usually handled by conventional techniques, such as the Kalman filter, the corresponding uncertainty due to noise usually being represented by a covariance matrix. The uncertainty in the origin of the measurements or data association problem typically has been largely ignored in the past though sometimes merged with the measurement noise. However, covariance matrices cannot represent the data association uncertainty.
We shall refer to the process of determining a robot's position as the process of localization.
This is a process of looking for and tracking expected and defined events. However, in most practical systems, there are occurrences that are unexpected and not well defined. Building maps of an environment for sensor information should involve maintaining a coherent map of expected events while evaluating and incorporation new, unexpected events as needed.
In two papers "entitled" Navigation by Correlating Geometric Sensor Data," authored by Hugh F. Durrant-Whyte and John J. Leonard, Proc. IEEE RSJ International Workshop on Intelligent Robots and Systems, (1989) Sep. 4-6, Tsukuba Japan, pp 440-447 and "Mobile Robot Localization" authored by J. J. Leonard and H. F. Durrant-Whyte, IEEE Transactions on Robotics and Automation, Vol 7 #3, (1991), there is described an autonomous mobile robot that utilizes a navigation system that reliably extracts geometric beacons from sensor data and utilizes them in automating a navigation system. The navigation algorithm of this system is based around a simple Kalman filter that is employed to estimate the position of the vehicle. The present invention basically involves improvements in a navigation system of the kind described in this paper and reference is made to such paper for background.